package fun.ticsmyc.question;


import org.junit.Test;

/**
 * 马拉车算法的变体应用
 *
 * @author Ticsmyc
 * @date 2020-04-12 12:28
 */
public class 字符串前后添加最少字符变回文串 {


    public static char[] toManacherStr(String str){
        char[] oldStr =str.toCharArray();
        char[] newStr = new char[2*oldStr.length +1 ];
        int index= 0;
        for (int i = 0; i < newStr.length; i++) {
            newStr[i] = (i&1) ==0? '#' :oldStr[index++];
        }
        return newStr;
    }

    /**
     * 往末尾添
     * @param str
     * @return
     */
    public String addToEnd(String str){
        char[] arr = toManacherStr(str);
        int[] pArr = new int[arr.length];

        int pR=-1; //右边界
        int index =0; //回文中心
        int startIndex =-1;

        for (int i = 0; i < pArr.length; i++) {
            pArr[i] = i<pR ? Math.min(pArr[2*index-i],pR-i) :1;
            while(i-pArr[i] >=0 && i+pArr[i]<arr.length){
                if(arr[i-pArr[i]] == arr[i+pArr[i]]){
                    pArr[i]++;
                }else{
                    break;
                }
            }
            if(i+pArr[i] >pR){
                index =i;
                pR =i+pArr[i];
            }
            //判断pR是否达到末尾
            if(pR ==arr.length){
                int x=1;
                startIndex = (index - pArr[i]+1)/2;
                break;
            }

        }
        StringBuilder sb = new StringBuilder(str.substring(0,startIndex));
        return sb.reverse().toString();
    }

    /**
     * 往开头添
     * @param str
     * @return
     */
    public String addToBegin(String str){
        char[] arr =toManacherStr(str);
        int[] pArr = new int[arr.length];

        int pL =pArr.length;  //左边界
        int index =arr.length-1; //回文中心

        int startIndex =-1;

        for (int i=pArr.length-1; i>=0; --i){
            pArr[i] = i>pL ? Math.min(pArr[2*index-i], i-pL):1;
            while(i-pArr[i] >=0 && i+pArr[i] < pArr.length){
                if(arr[i-pArr[i]] ==arr[i+pArr[i]]){
                    pArr[i]++;
                }else{
                    break;
                }
            }
            if(i-pArr[i] <pL){
                index= i;
                pL = i-pArr[i];
            }
            if(pL==-1){
                //扩到头了 ，这个子串满足要求
                startIndex  = (index+pArr[i]-1)/2;
                break;
            }
        }
        StringBuilder sb = new StringBuilder(str.substring(startIndex,str.length()));

        return sb.reverse().toString();

    }

    @Test
    public void testManacherString() {
        String str = "how are you";
        char[] res = toManacherStr(str);
        for (char s : res) {
            System.out.print(s);
        }
    }
    @Test
    public void testManacher() {
//        String str = "asdfabccba";
//        System.out.println(str+"  "+addToEnd(str));

        String str2 = "abccbadf";
        System.out.println(addToBegin(str2)+"  "+str2);
    }
}
